Today's network links carry vast amounts of information. High bandwidth applications supported by these network links include, for example, streaming video, streaming audio, and large aggregations of voice traffic. In the future, network bandwidth demands are certain to increase.
As a business grows, so can its network, increasing in the number of network elements coupled to the network, the number of network links, and also geographic diversity. Over time, a business' network can include physical locations scattered throughout a city, a state, a country, or the world. Since it can be prohibitively expensive to create a private network that spans these great distances, many businesses opt to rely upon a third-party provider's transport network to provide connectivity between the disparate geographic sites of the business' network elements. In order for the business' network to seamlessly function through the transport network, the transport network must be able to provide a medium for transmission of all the business' various types of datastreams, including multicast transmission.
Multicast routing protocols enable multicast datastream transmission (i.e., one-to-many connections and many-to-many connections) by replicating a multicast data packet close to the destinations of that packet, thereby obviating the need for multiple unicast connections for the same purpose; thus, saving network bandwidth and improving throughput. Upon receiving a multicast packet, a network node (e.g., a router) can examine a multicast group destination address (GDA) of the packet and determine whether downstream subscribers to the multicast packet (i.e., members of the multicast group) are connected to the network node (either directly or indirectly). The network node can then replicate the multicast packet as needed and transmit the replicated packets to any connected subscribers.
FIG. 1A is a simplified block diagram of a network transporting a multicast transmission. Network router elements 110, 120, 130 and 140 are coupled through network links 150, 160, and 170. Network router element 110 is also coupled to network elements 111 and 112; network router element 120 is coupled to network element 121; network router element 130 is coupled to network elements 131 and 132; and, network router element 140 is coupled to network element 141. Such coupling between the network router elements and the network elements can be direct or indirect (e.g., via a L2 network device or another network router element).
For the purposes of this illustration, network element 111 is a multicast source transmitting a datastream to a multicast group that includes network elements 112, 121, 131, 132 and 141. A multicast datastream, having a group destination address to which the above network elements have subscribed as receiver members, is transmitted from network element 111 to network router element 110 (illustrated by the arrow from 111 to 110). Network router element 110 determines where to forward packets in the multicast datastream by referring to an internal address table that identifies each port of network router element 110 that is coupled, directly or indirectly, to a subscribing member of the multicast group. Network router element 110 then replicates packets of the multicast datastream and then transmits the packets from the identified ports to network element 112, network router element 120 and network router element 130.
Network router elements 120 and 130 can inform network router element 110 that they are coupled to a subscribing member of a multicast datastream using, for example, a protocol independent multicast (PIM) message. Using PIM, network router elements 120 and 130 can send messages indicating that they need to join (a “JOIN” message) or be excluded from (a “PRUNE” message) receiving packets directed to a particular multicast group or being transmitted by a particular source. Similarly, a network element can inform a first-hop network router element that the network element wishes to be a subscriber to a multicast group by sending a membership report request through a software protocol such as internet group management protocol (IGMP). When a network element wishes to subscribe to a multicast transmission, an IGMP membership request frame can be transmitted by the network element. An IGMP-enabled network router element (or a L2 network device) can have “snooping” software executing to read such a frame and build a corresponding entry in a multicast group address table.
Upon receipt by network router elements 120 and 130, packets from the multicast datastream will be replicated as needed by those network router elements to provide the multicast datastream to network elements coupled to those network router elements (e.g., network elements 131 and 132 or network router element 140). In this manner, a multicast datastream from network element 111 can be transmitted through a network to multiple receiving network elements. The path of such a transmission can be thought of as a tree, wherein network element 111 is the root of the tree and network elements 121, 131, 132, and 141 can be thought of as the tips of branches.
FIG. 1B is a simplified block diagram of a network in which multiple sources are transmitting to a multicast group. As in FIG. 1A, network element 111 is a source for a multicast datastream directed to a multicast group including network elements 112, 121, 131, 132, and 141. That multicast datastream is illustrated by path 180 (a solid line). Network element 132 is also transmitting a multicast datastream to the multicast group, and that datastream is illustrated by path 190 (a dashed line). In a multiple source multicast group, any subscriber network element can be a source. In order to provide this two-way routing of multicast data packets, a bi-directional version of protocol independent multicast (PIM bidir) is used to configure the network router elements in the multicast tree. In bi-directional multicast, datastream packets are routed only along the shared bi-directional tree, which is rooted at a rendezvous point for the multicast group, rather than at a particular datastream source. Logically, a rendezvous point is an address (e.g., a network router element) that is “upstream” from all other network elements. Passing all bi-directional multicast traffic through a rendezvous point establishes a loop-free tree topology having the rendezvous point as a root. In FIG. 1B, the rendezvous point is illustrated as network router element 110.
FIGS. 1A and 1B illustrate transmission of multicast datastreams in a network in which the network router elements 110, 120, 130 and 140 are directly coupled with one another. But, as stated above, as a business and its network grow, a business' network elements can become geographically diverse and therefore the path over which the datastream must flow can include an intervening third-party provider transport network.
FIG. 2 is a simplified block diagram illustrating a network configuration in which geographically diverse subnets of a business' network are coupled through a transport network 200. The business' network includes network router elements 210, 220, 230, and 240, wherein network router element 210 is coupled to network elements 211 and 212, network router element 220 is coupled to network element 221, network router element 230 is coupled to network elements 231 and 232, and network router element 240 is coupled to network element 241. In order to connect to the transport network, a network router element on the edge of the business' network (a customer edge router) is coupled to a network router element on the edge of the transport network (a provider edge router (PE)). In FIG. 2, customer edge router elements 250(1)-(3) are coupled to PEs 260(1)-(3), respectively. Network router element 240 is coupled to PE 260(4) (that is, network router element 240 is configured as a customer edge router). It should be noted that the terms “provider edge router” and “customer edge router” are used to distinguish between an edge router that is a member of a transport network (a provider edge router) and an edge router that is a member of a network external to the transport network (a customer edge router). Such terms are not meant to limit the discussion or the invention presented herein to networks of a third-party provider and customers of the provider.
The customer edge router and the provider edge router functionality can be provided by a single router. Further, a network router element such as 240 can also serve as an edge router. The provider edge routers provide access to the transport network which can contain data transmission lines, network router elements, and OSI Level 2 network devices to aid in the transmission of data packets from one provider edge router to another provider edge router. The transport network illustrated in FIG. 2 contains, as an example, network router elements 270(1)-(5) and 270(r), which are coupled in a manner to permit transmission of packets through the transport network. Such network router elements internal to a transport network are called “core router elements” or “core routers.” A transport network is not limited to such a configuration, and can include any number of network router elements, transmission lines, and other L2 and L3 network devices.
In order to facilitate transmission of data packets through a transport network, the transport network can utilize different protocols from those used in coupled customer networks. Such transport network protocols can permit faster or more efficient data transmission and routing through the network. Any needed translation between customer and transport network protocols can be performed by the edge routers.
FIG. 3 is a simplified block diagram illustrating another representation of a transport network 300. It should be understood that the term “transport network” corresponds to any network of coupled network router elements including edge network router elements (“edge routers”) and core network router elements (“core routers”) as those terms are understood in the art. FIG. 3 illustrates a set of transport network edge routers 320(1)-(4). These edge routers are connected by a network including core routers 310(1)-(6) and 315(1)-(2). Using transport network protocols, such as MPLS or tunneling protocols, a datastream can be transmitted from an edge router to any other edge router via a subset of the core routers in the transport network. A datastream can also be transmitted from an edge router to a plurality of other edge routers via a configured point-to-multipoint path through the core of the transport network; such a configured path is called a transport tree. A transport tree can also be configured to transport datastreams from a plurality of transmitting edge routers to a plurality of other edge routers via a multipoint-to-multipoint configured path through the core of the transport network; such a transport tree can be specifically called a multipoint-to-multipoint transport tree.
FIG. 4A is a simplified block diagram illustrating relevant components of a multipoint-to-multipoint transport tree configured in transport network 300 of FIG. 3. A multicast datastream source S1 is coupled, directly or indirectly, to edge router 320(1), which is configured as an ingress router to the transport network for a datastream originating with source S1. Edge routers 320(2)-(4) are egress routers for the datastream from source S1 to exit the transport network en route to subscribers for the multicast datastream. Datastream packets from source S1 flow through network core routers along the path illustrated by solid arrows through transport network 300. Similarly, a multicast datastream source S2 is coupled to edge router 320(4), which serves as an ingress router to the transport network for a datastream from source S2. Edge routers 320(1)-320(3) are egress routers for the datastream from source S2 to exit the transport network en route to subscribers for the multicast datastream. Datastream packets from source S2 can flow through transport network 300 core routers along a path illustrated by the dashed arrows. Transport network core routers 310(1)-(6) and 315(1) can transmit and replicate packets from the two datastreams, as necessary.
In a multipoint-to-multipoint transport tree, datastreams must be able to flow “downstream” from a source to a group of receivers and also “upstream” from each receiver acting as a source to each other receiver of the group. Similar to bi-directional multicast trees, in order to permit loop-free, upstream data flow, a root node is established within the transport network. Each transport network router will be configured to find a path to the root node. When a multipoint-to-multipoint transport tree is configured, the root node is selected for that transport tree. Typically, a root node is chosen to be convenient and well-connected to all edge routers that may become members of the transport tree. Edge routers can be informed of the identity of a root node associated with a transport tree when that transport tree is constructed. Static configuration of the edge routers can be used to inform the edge routers of the identity of a root node associated with a transport tree.
In FIG. 4A, core router 315(1) is the root node of the illustrated multipoint-to-multipoint transport tree. From the perspective of each edge router not coupled to a multicast datastream source and each intermediate core router, the root node is always considered to be in the upstream direction. Thus, datastream packets transmitted on the multipoint-to-multipoint transport tree will first be directed to the root node and from there will be directed toward member edge routers via the core routers.
The root node in a multipoint-to-multipoint transport tree serves a role as a hub of datastream transport through the transport tree. In the event of failure of a root node, datastream transport on the associated transport tree will also fail. In a typical transport network, recovery from failure of a transport tree root node requires constructing a new transport tree with an associated new root node.
FIG. 4B is a simplified block diagram illustrating a second multipoint-to-multipoint transport tree configured in transport network 300 to transport the multicast datastreams from sources S1 and S2. It is noted that datastream packets from S1 and S2 have the same multicast group destination address. Rather than routing the datastreams through failed core router 315(1) (which served as the root node for the transport tree illustrated in FIG. 4A), the second transport tree has a selected root node at core router 315(2). Building such a second transport tree re-establishes multipoint-to-multipoint communications, but communications are disrupted during the time to build the second transport tree. The length of time to create the new transport tree can be affected by activities such as detection of the failure of root node 315(1), coordinating the building activities of the various edge network router elements, and reestablishing a link between the native transport trees of sources S1 and S2 (e.g., multicast transport trees).
A mechanism is therefore desired to decrease or eliminate the amount of time of disruption in communications due to the failure of a root node.